package com.Questions.DP;


/**
 *  跳跃游戏2
 */
public class leetcode45 {
    // 自己想的动态规划 算法是正确的 只不过时间复杂度过高
    // 导致超时
//    public int jump(int[] nums) {
//        int n=nums.length;
//        int MaxValue=100000;
//        int [][]dp=new int[n][n];
//        for(int i=0;i<n;++i){
//            for(int j=0;j<n;++j){
//                dp[i][j]=MaxValue;
//            }
//        }
//        for(int i=0;i<n;++i){
//            dp[i][i]=0;
//        }
//        for(int L=2;L <= n;L++){
//            for(int i = 0;i < n ;++i){
//                int j=L+i-1;
//                if(j>=n){
//                    break;
//                }
//                if(j-i<=nums[i]){// 能一步到达
//                    dp[i][j]=1;
//                }else{// 不能一步到达
//                    int min=MaxValue;
//                    for(int k=i+1;k<j;++k){
//                        min=Math.min(dp[i][k]+dp[k][j],min);
//                    }
//                    dp[i][j]=min;
//                }
//            }
//        }
//        return dp[0][n-1];
//    }
    public int jump(int[] nums) {
        int n=nums.length;
        int[] dp=new int[n];
        for(int i=0;i<n;++i){
            dp[i]=100000;
        }
        dp[0]=0;
        for(int i=1;i<n;++i){
            for(int j=0;j<i;++j){
                if(nums[j]+j>=i){// 如果j位置能达到 i 则将
                    dp[i]=Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[n-1];
    }

}
